1. Field of the Invention
This invention relates to the field of data communications networks. More particularly, this invention relates to a method and apparatus for implementing a quality of service (QoS) policy in a data communications network so as to thereby prioritize network traffic into a plurality of service levels and provide preferential treatment of different classes of data traffic on the data communications network. A number of priority levels may be implemented in accordance with the invention.
2. Background
This invention relates to switched packet data communications networks. There are a number of different packet types which are used in modern switched packet data communications networks.
FIG. 1 A depicts a generic packet 8 using Layer 2 encapsulation. A number of different Layer 2 encapsulation protocols are recognized. Each may include a MAC (media access control) destination address 10 and a MAC source address 12. The data 14 may include Layer 3 encapsulated packet information. A CRC (cyclic redundancy check) 16 may also be provided at the end of the Layer 2 encapsulation. The unlabeled block 18 may include an Ethernet type for Ethernet V 2.0 (ARPA) packets. The Ethernet type may include IPv4 (IP), IPX, AppleTalk, DEC Net, Vines IP/Vines Echo, XNS, ARP or RARP. Other known encapsulations include SAP, SAP1, SNAP and the like. The meaning of the bits in and the size of block 18 differs among the different encapsulation protocols. This information is sometimes referred to as the Layer 2 Flow Information.
One special case of Layer 2 encapsulation is the IEEE 802.1 q frame shown schematically in FIG. 1B. The IEEE 802.1 q frame (or packet) 20 has a MAC Destination Address (xe2x80x9cDAxe2x80x9d) 10, MAC Source Address (xe2x80x9cSAxe2x80x9d) 12, Data Portion 14 and CRC 16. In addition, within block 18 is the IEEE 802.1 q xe2x80x9ctagxe2x80x9d 22 which includes, among other items, a block of three priority bits 24. These three bits are also known as a xe2x80x9cClass of Servicexe2x80x9d or xe2x80x9cCoSxe2x80x9d field.
FIG. 1C depicts the Layer 3 and Layer 4 structure of a typical IP packet The IP packet format will be detailed here by way of example because it is presently one of the most common Layer 3 packet types. The fields of importance to this disclosure are the xe2x80x9cToS valuexe2x80x9d or type of service 26 which is a preferably 8-bit field also known as the Differentiated Service (xe2x80x9cDSxe2x80x9d) field, xe2x80x9cprot-typxe2x80x9d or IP protocol type 28 (typically either TCP 20 (transmission control protocol) or UDP (user datagram protocol)), the Source IP address 30 (usually the IP address of the originating station), the Destination IP address 32 (usually the IP address of the ultimate destination station), the Layer 4 source port number 34 (available for TCP and UDP packets only) and the Layer 4 destination port number 36 (available for TCP and UDP packets only). The Layer 3 flow information includes the information before the source port number 34. The Layer 4 flow information includes the Source and Destination ports 34, 36. The Layer 4 flow information may be used to identify a particular packet flow as being the product of (source port) or directed to (destination port) a particular application. The ToS and CoS fields are used by routers of the data communications network to provide priority/delay/dropping services.
As the use of data communications networks increases worldwide, congestion of those networks has become a problem. A given data communications network, a given node on a data communications network, or a given link connecting two nodes has a certain capacity to pass data packets and that capacity cannot be exceeded. When data traffic on the data communications network becomes heavy enough that one can anticipate congestion problems, it is desirable to implement a xe2x80x9cQuality of Servicexe2x80x9d or QoS policy so as to give priority to certain types of traffic and restrict the flow of other types of traffic, thus assuring that critical communications are able to pass through the data communications network, albeit at the expense of less critical communications.
One of the problems that network devices face in implementing quality of service solutions is in identifying and grouping transmissions to be given preferential treatment or to be restricted, that is, to prioritize the traffic in accordance with the Quality of Service policy established for the network. This becomes especially critical as bandwidth increases substantially over certain links while other links remain relatively slow resulting in traffic speed mismatches which, in turn, cause bottlenecks to data traffic over the relatively slow links. Such groupings must be consistently applied to traffic and must be applied at the rate that the traffic is passing without introducing additional delays or bottlenecks. Such groupings may be, for example, by protocol type, by destination IP address, by source IP address, by destination/source IP address pair, by source port and/or destination port (Layer 4), and the like.
Routers have, in the past, kept packet counts and rate limited packets in software, but router software has not scaled to the level of being able to process millions of packets per second through a node, providing the basic routing functions that they are required to provide and being able to also provide the rate limitation function.
One approach to identifying and grouping transmissions is for the host to categorize packets by use of the L2 CoS field, L3 ToS field or both. The primary disadvantage of this approach is that it removes control from the system administrator and requires one to trust the end stations to the communication to properly implement the QoS policy. In some cases this trust cannot be justified. In addition, an end station only sees its own packets and therefore is unaware of the overall resource requirements within the data communications network and cannot make allowances for these requirements.
Accordingly, a Quality of Service policy controlled by a network system administrator is needed together with a mechanism for applying it at the full data rate of the data communications network.
In a first aspect of the invention a content addressable memory (CAM or L3 Table) contains flow information for each active flow of packets passing through a given node of a data communications network. The CAM has associated with each entry (corresponding to each active flow) a packet counter, a number of bytes seen counter, a token bucket and a contract value or committed access rate. Each flow is assigned one of a plurality of output queues and optionally at least one output queue threshold value. A token bucket algorithm is employed on each flow to determine whether packets from that flow exceed a committed access rate. Such packets may be dropped or optionally modified to reflect an alternate output queue and/or alternate output queue threshold value before being sent to the selected output queue for transmission from the node.
In a second aspect of the invention an access control list CAM (ACLCAM) contains masked flow information such as, for example, all or portions of IP source and/or destination addresses, protocol types and the like. The ACLCAM provides single clock cycle accesses when performing lookups for each packet. The ACLCAM provides an N-bit index value in response to QoS lookups based upon the best match for the current packet.
The best match is order dependent for the entry in the ACLCAM and may represent any fields in the packet upon which the administrator of the data communications network wishes to base traffic rate limiting and prioritizing decisions. A plurality of ACLCAM entries can yield the same N-bit index value. The N-bit ACLCAM index selects one of 2N internal counters and associated preconfigured contract values, which become affected by the packet statistics. A token bucket algorithm is employed on these counters as discussed above.
The ACL CAM may also be used to determine the QoS parameters for new entries in the L3 Table as they are created. In addition, it is used to select an entry in the aggregate flow table described below.
In a third aspect of the invention, an aggregate flow table contains information specifying plural flowsxe2x80x94for example all traffic between x and y regardless of type, all traffic to x of a certain type, all traffic from anyone of a certain type, and the like. These specifications may specify more than one flow. This is possible because each entry has a corresponding flow mask. This is different from the L3 Table which may identify certain specific flows only, i.e., all traffic of protocol type HTTP from x to y. Since the entire L3 Table operates with a single flow mask, each entry will have identical specificity, thus, there could be multiple entries for traffic from x to y if such traffic includes multiple protocol types and the flow mask does not mask the protocol type, for example.
In a fourth aspect of the invention, the CAM, an aggregate flow table and the ACLCAM are combined in one system and used to produce, in parallel, a pair of traffic rate limiting and prioritizing decisions for each packet. The two results are then resolved (if in conflict) to yield a single result which is acted upon. The result is to modify or not modify the packet""s CoS and/or ToS (or other) fields and to drop or pass the packet onto the next node of the data communications network.